The eccentricity of a node in a graph is defined as the length of a longest shortest\r\npath starting at that node. The eccentricity distribution over all nodes is a relevant descriptive\r\nproperty of the graph, and its extreme values allow the derivation of measures such as the\r\nradius, diameter, center and periphery of the graph. This paper describes two new methods\r\nfor computing the eccentricity distribution of large graphs such as social networks, web\r\ngraphs, biological networks and routing networks.We first propose an exact algorithm based\r\non eccentricity lower and upper bounds, which achieves significant speedups compared to the\r\nstraightforward algorithm when computing both the extreme values of the distribution as well\r\nas the eccentricity distribution as a whole. The second algorithm that we describe is a hybrid\r\nstrategy that combines the exact approach with an efficient sampling technique in order to\r\nobtain an even larger speedup on the computation of the entire eccentricity distribution. We\r\nperform an extensive set of experiments on a number of large graphs in order to measure\r\nand compare the performance of our algorithms, and demonstrate how we can efficiently\r\ncompute the eccentricity distribution of various large real-world graphs.
Loading....